/*
 * @lc app=leetcode.cn id=127 lang=typescript
 *
 * [127] 单词接龙
 */

// @lc code=start

interface WordNode {
  word: string;
  step: number;
}

function ladderLength(beginWord: string, endWord: string, wordList: string[]): number {
  const base = 'a'.charCodeAt(0);
  const hash = new Set(wordList);
  // 字典中不包含终点单词，肯定完成不了转换
  if (!hash.has(endWord)) return 0;
  // 搜索起点
  const queue: WordNode[] = [{ word: beginWord, step: 1 }];
  // 开始搜索
  while (queue.length) {
    let curr = queue.shift();
    // 搜索到终点
    if (curr.word === endWord) {
      return curr.step;
    }
    // 当前单词的所有可能的转换
    // 改变单词的每个字符，从 a - z 枚举
    for (let i = 0; i < curr.word.length; i++) {
      const temp = curr.word.split('');
      for (let j = 0; j < 26; j++) {
        const char = String.fromCharCode(base + j);
        temp[i] = char;
        const word = temp.join('');
        // 如果字典中包含，并且没有被访问过，加入队列
        if (hash.has(word)) {
          // 删除字典中的单词，已访问过
          hash.delete(word);
          queue.push({ word, step: curr.step + 1 });
        }
      }
    }
  }

  return 0;
}
// @lc code=end
